package basic.courseLearn16.problem;

import org.junit.Test;

import java.util.Arrays;

//给定货币序列和一个目标金额，求组成目标金额的方法数
public class ComposeAmount {

    @Test
    public void test_solution_1(){
        int[] nums = {1, 2, 5};
        int target = 11;
        int ways = solution_1(nums, 0, target);
        System.out.println(ways);
    }

    @Test
    public void test_solution_2(){
        int[] nums = {1, 2, 5};
        int target = 11;
        //定义记忆表
        int[][] memo = new int[nums.length][target + 1];
        for (int i = 0; i < memo.length; i++) {
            for (int j = 0; j < memo[0].length; j++) {
                memo[i][j] = -1;
            }
        }
        int ways = solution_2(memo,nums, 0, target);
        System.out.println(ways);
    }

    @Test
    public void test_solution_3(){
        int[] nums = {1, 2, 5};
        int target = 11;

        int ways = solution_3(nums, 0, target);
        System.out.println(ways);
    }

    @Test
    public void test_solution_4(){
        int[] nums = {1, 2, 5};
        int target = 11;

        int ways = solution_4(nums, 0, target);
        System.out.println(ways);
    }

    @Test
    public void check(){
        int count = 1_00;
        int nums_range = 5;
        int nums_count_range = 10;
        int target_range = 1_00;
        System.out.println("开始测试");
        for (int i = 0; i < count; i++) {
            System.out.println("第" + (i+1) + "次测试");
            int nums_count = (int)(Math.random() * nums_count_range) + 1;//[1,100]
            int[] nums = new int[nums_count];
            for (int j = 0; j < nums_count; j++) {
                nums[j] = (int)(Math.random() * nums_range) + 1; //[1,100]
            }
            int target = (int)(Math.random() * target_range) + 1; //[1,1000]
            int ways1 = solution_1(nums, 0, target);
            int[][] memo = new int[nums.length][target + 1];
            for (int index = 0; index < memo.length; index++) {
                for (int j = 0; j < memo[0].length; j++) {
                    memo[index][j] = -1;
                }
            }
            int ways2 = solution_2(memo,nums, 0, target);
            int ways3 = solution_3(nums, 0, target);
            int ways4 = solution_4(nums, 0, target);
            if(ways1!= ways2 || ways1!= ways3 || ways1!= ways4){
                System.out.println("error");
                System.out.println("nums: " + Arrays.toString(nums)
                        + " target: " + target
                        + " ways1: " + ways1
                        + " ways2: " + ways2
                        + " ways3: " + ways3
                        + " ways4: " + ways4);
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 方法1：暴力递归
     * @param nums 货币序列
     * @param index 当前处理的货币序号
     * @param target 目标金额
     * @return 组成目标金额的方法数
     */
    public int solution_1(int[] nums,int index, int target){
        //1. 边界问题
        if (target < 0){
            return 0;
        }
        if(index == nums.length){
            return target == 0? 1 : 0;
        }
        //2. 递归计算
        int ways = 0;
        //选当前货币
        for (int i = 0; target - nums[index] * i >= 0; i++) {
            ways += solution_1(nums, index + 1, target - nums[index] * i);
        }
        return ways;
    }

    /**
     * 方法2：记忆表搜索
     * @param memo 记忆表
     * @param nums 货币序列
     * @param index 当前处理的货币序号
     * @param target 目标金额
     * @return 组成目标金额的方法数
     */
    public int solution_2(int[][] memo,int[] nums,int index, int target){
        //1. 边界问题
        if (target < 0){
            return 0;
        }
        if(index == nums.length){
            return target == 0? 1 : 0;
        }
        //2. 判断是否已经计算过
        if(memo[index][target]!= -1){
            return memo[index][target];
        }
        //3. 递归计算
        int ways = 0;
        //选当前货币
        for (int i = 0; target - nums[index] * i >= 0; i++) {
            ways += solution_2(memo, nums, index + 1, target - nums[index] * i);
        }
        memo[index][target] = ways;
        return ways;
    }

    /**
     * 方法3：严格表结构-基础
     * @param nums 货币序列
     * @param index 当前处理的货币序号
     * @param target 目标金额
     * @return 组成目标金额的方法数
     */
    public int solution_3(int[] nums,int index, int target){
        //1. 初始化严格表
        int[][] memo = new int[nums.length+1][target+1];
        for (int j = 0; j < target+1; j++) {
            if (j==0){
                memo[nums.length][j] = 1;
            }else{
                memo[nums.length][j] = 0;
            }
        }
        //2. 填值计算
        for (int i = nums.length-1; i >= 0; i--) {
            for (int j = 0; j <= target; j++) {
                int ways = 0;
                //选当前货币
                for (int count = 0; j - nums[i] * count >= 0; count++) {
                    ways += memo[i+1][j-nums[i]*count];
                }
                memo[i][j] = ways;
            }

        }

        return memo[0][target];
    }

    /**
     * 方法4：严格表结构-枚举优化
     * @param nums 货币序列
     * @param index 当前处理的货币序号
     * @param target 目标金额
     * @return 组成目标金额的方法数
     */
    public int solution_4(int[] nums,int index, int target){
        //1. 初始化严格表
        int[][] memo = new int[nums.length+1][target+1];
        for (int j = 0; j < target+1; j++) {
            if (j==0){
                memo[nums.length][j] = 1;
            }else{
                memo[nums.length][j] = 0;
            }
        }
        //2. 填值计算
        for (int i = nums.length-1; i >= 0; i--) {
            for (int j = 0; j <= target; j++) {
                int ways = memo[i+1][j];
                if (j - nums[i] >= 0){
                    ways += memo[i][j-nums[i]];
                }
                memo[i][j] = ways;
            }

        }

        return memo[0][target];
    }



}
